package middle;

import java.util.ArrayList;
import java.util.List;

public class Solution_95 {

    public List<TreeNode> generateTrees(int n) {
        return dps(1, n);
    }

    private List<TreeNode> dps(int begin, int end) {
        List<TreeNode> roots = new ArrayList<>();
        if (begin > end) {
            roots.add(null);
        } else {
            for (int i = begin; i <= end; i++) {
                List<TreeNode> leftNodes = dps(begin, i - 1);
                List<TreeNode> rightNodes = dps(i+1, end);
                for (TreeNode leftNode : leftNodes) {
                    for (TreeNode rightNode : rightNodes) {
                        TreeNode root = new TreeNode(i);
                        root.left = leftNode;
                        root.right = rightNode;
                        roots.add(root);
                    }
                }
            }
        }
        return roots;
    }

    public static void main(String[] args) {
        Solution_95 model = new Solution_95();
        List<TreeNode> trees = model.generateTrees(1);
        System.out.println(trees);
    }

    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
